package com.chapter4.graph.direct;

import java.util.Stack;

/**
 * 
* @ClassName: Topological 
* @Description: 拓扑排序
* @author minjun
* @date 2015年3月2日 上午7:41:16 
*
 */
public class Topological {

	private boolean[] marked;
	
	private Stack<Integer> reversePost;
	
	public Topological(Digraph d){
		
		DirectedCycle dc=new DirectedCycle(d);
		if(dc.hasCycle()){
			System.out.println("有环");
			return;
		}
		int len=d.V();
		marked=new boolean[len];
		reversePost=new Stack<Integer>();
		for(int i=0;i<len;i++){
			if(!marked[i]){
				dfs(d,i);
			}
		}
	}

	private void dfs(Digraph d, int v) {
		marked[v]=true;
		for(int w:d.adj(v)){
			if(!marked[w]){
				dfs(d, w);
			}
		}
		reversePost.push(v);
	}
	
	public Iterable<Integer> reversePost(){
		return reversePost;
	}
}
